package demo19;

import java.lang.reflect.Array;
import java.util.Arrays;

public class dun {
    int elem[];
    int useSize;
    public dun(){
        elem=new int[10];
    }
    //初始化大根堆
    public void initial(int[]array){
        for(int i=0;i<array.length;i++){
           this.elem[i]=array[i];
            this.useSize++;
        }
        deal();
    }
    //调整大根堆
    public void deal(){
        for(int p=(useSize-1)/2;p>=0;p--){
            shitfDown(p);
        }
    }
    public void shitfDown(int parent){    //向下调整，从最后一个非叶子节点开始向前一一判，因为其前节点可能都违规
        int child=(parent+1)/2;
        int len=useSize;
        while (child<len){
            if(child+1<len&&elem[child+1]>elem[child]){
                child++;
            }
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    public void swap(int[]elem,int child,int parent){   //交换
        int temp=elem[child];
        elem[child]=elem[parent];
        elem[parent]=temp;
    }
    //打印
    public void display(){
        for(int i=0;i<useSize;i++){
            System.out.print(elem[i]+" ");
        }
    }
    //向上调整
    public void insert(int num){
        if(full()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        useSize++;
        elem[useSize-1]=num;
        shiftup(useSize-1);

    }
    public void shiftup(int child){//
        int parent=(child-1)/2;
        while (child>0){//未到根就一直调
            if(elem[parent]<elem[child]){
                swap(elem,child,parent);
                child=parent;//继续向上爬
                parent=(child-1)/2;
            }else {
                break;
            }
        }
        display();
    }
    public boolean full(){//判满
        return useSize==elem.length;
    }
    public boolean empty(){
        return useSize==0;
    }
    public void peek(){
        if(empty()){
            System.out.println("堆顶为空！");
            return;
        }
        System.out.println();
        System.out.println("堆顶元素为：");
        System.out.println(elem[0]+" ");
        System.out.println();
    }
//取出栈顶元素
    public void poll(){
        if(empty()){
            System.out.println("堆顶为空！");
            return;
        }
        System.out.println();
        System.out.println("取出堆顶元素：");
        System.out.println(elem[0]+" ");
        int temp=elem[0];
        swap(elem,0,useSize-1);
        shitfDown(0);//只有根节点违规从根开始
        useSize--;
        System.out.println("去掉堆顶元素为：");
        display();
    }
//删除堆中元素
    public void delect(int num2) {
                                                                //第一种删除方法
                                                                //        for (int i = 0; i < useSize; i++) {
                                                                //            if (num2 == elem[i]) {
                                                                //                for (int k = i; k < useSize; k++) {
                                                                //                    elem[k] = elem[k + 1];
                                                                //                }
                                                                //                useSize--;
                                                                //                shiftup(useSize);
                                                                //                return;
                                                                //            }
                                                                //        }
        for(int i=0;i<useSize;i++){//第二种删除方法
            if(num2==elem[i]){
                elem[i]=elem[useSize-1];//不需要管上面的，因为删去的节点比上面的小比下面的大
                useSize--;
                int k=i;
                shitfDown(k);
                display();
                return;
            }
        }
            System.out.println("堆中没有这个数！");
            System.out.println();
        }


}
